package com.frx.leetoffer.dayone;

import java.util.Arrays;

/**
 * @author xurenfeng
 * @decription 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，
 * 但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
 * Input {2,3,1,0,2,5}
 * Output 2
 */
public class ArrayRepeat {

    public static void main(String[] args){

        int[] arr = new int[]{2,3,1,0,1,2,5};
        int[] dp = new int[6];
/*
        System.out.println(repeat(arr));*/
        int [] dup = new int[2];
/*
        if(duplicate(arr,arr.length,dup)){
            System.out.println(dup[0]);
        }*/


    }



    /** 使用了一个额外的标记数据来求解*/
    public static int repeat(int[] arr){
        int[] arr2 = new int[arr.length];
        for (int i=0;i<arr.length;i++){
            arr2[arr[i]]++;
        }
        System.out.println(Arrays.toString(arr2));
        for (int i=0;i<arr2.length;i++){
            if (arr2[i] > 1){
                return i;
            }
        }
        return 0;
    }

    /**
     * @description 要求时间复杂度O(N),空间复杂度O(1)
     * 因此不能使用排序的方法，也不能使用额外数组的方法
     */
    public static boolean duplicate(int numbers[],int length,int [] duplication) {

        if(null == numbers || 0 == length){
            return false;
        }
        for(int i=0;i<length;i++){

            while(i != numbers[i]){
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                int j = numbers[i];
                int temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }
        return false;
    }
}
